package lc.二叉树.剑指Offer;

import utils.TreeNode;

/**
 * @description:
 * @author: qian
 * @createDate: 2021/10/18
 */
public class Math剑指Offer26_树的子结构 {



    public boolean isSubStructure(TreeNode A, TreeNode B) {

        if (A == null && B == null) return true;
        // 根节点能找到或者根节点的左孩子能找到 根节点的右孩子能找到
        return isSub(A,B) || isSubStructure(A.left,B) || isSubStructure(A.right,B);
    }

    private boolean isSub(TreeNode a, TreeNode b) {

        if (b == null) {
            return true;
        }
        if (a == null) { // b里面还有没匹配到的值
            return false;
        }
        if (a.val != b.val) return false;

        return isSub(a.left,b.left) && isSub(a.right,b.right);
    }
}
